//  On my honor:
//	
//  - I have not used source code obtained from another student, 
//    or any other unauthorized source, either modified or unmodified.  
//	
//  - All source code and documentation used in my program 
//    is either my original work, or was derived by me from the source
//    code published in the textbook for this course.
//	
//  - I have not discussed coding details about this project with anyone
//    other than my instructor, ACM/UPE tutors or the GTAs assigned to this
//    course. I understand that I may discuss the concepts of this program
//    with other students, and that another student may help me debug my
//    program so long as neither of us writes anything during the discussion
//    or modifies any computer file during the discussion.  I have violated
//    neither the spirit nor letter of this restriction.
//	

import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author Christopher Suh, Eric Yoo
 * 
 */
public class BTree {
	private TreeNode<City> root; // root of the tree
	private int nodecount; // number of nodes in the tree
	private Comparator<String> c;
	private BufferPool pool;
	
	BTree(Comparator<String> c, BufferPool p) {
		root = null;
		nodecount = 0;
		this.c = c;
		pool = p;
	}

	public ArrayList<City> findAll(String k) {
		return findAllhelp(root, k);
	}

	/**
	 * searches the BST for the element with key k
	 * 
	 * @param k
	 *            key of the element being searched for
	 * @return the element of the searched item
	 */
	public City find(String k) {
		return findhelp(root, k);
	}

	/**
	 * inserts the element e with key k to a valid location in the tree
	 * 
	 * @param k
	 *            key of element being inserted
	 * @param e
	 *            element being inserted
	 */
	public void insert(String n, Integer k, City c) {
		
		root = inserthelp(root, n, k, c, false);
		nodecount++;
	}

	/**
	 * removes the given element. if none is found, null is returned
	 * 
	 * @param k
	 *            key of the removed element
	 * @return element of the removed node
	 */
	public City remove(String k) {
		City temp = findhelp(root, k);
		if (temp != null) {
			root = removehelp(root, k);
			nodecount--;
		}
		
		return temp;
	}

	/**
	 * removes the node with the given key and coordinate
	 * 
	 * @param k
	 *            key of the removed element
	 */
	public void remove(String k, City c) {
		root = removehelp(root, k, c);
		nodecount--;
	}

	/**
	 * inserts the given element to its right location in the tree
	 * 
	 * @param rt
	 *            root of subtree
	 * @param k
	 *            Key of element being inserted
	 * @param e
	 *            element being inserted
	 * @param flag
	 *            flag to check whether current node is equal to its parent node
	 * @return return the current subtree, modified to contain the new item
	 */
	private TreeNode<City> inserthelp(TreeNode<City> rt, String n, Integer k, 
			City e, boolean flag) {
		if (flag) {
			TreeNode<City> temp = new TreeNode<City>(k, e);
			temp.setLeft(rt);
			return temp;
		} else {
			if (rt == null)
				return new TreeNode<City>(k, e);
			if (c.compare(readStringFromPool(rt.key()), n) > 0)
				rt.setLeft(inserthelp(rt.left(), n, k, e, false));
			else if (c.compare(readStringFromPool(rt.key()), n) == 0)
				rt.setLeft(inserthelp(rt.left(), n, k, e, true));
			else
				rt.setRight(inserthelp(rt.right(), n, k, e, false));
			return rt;
		}
	}

	/**
	 * Remove a node with key value k
	 * 
	 * @param rt
	 *            root of subtree
	 * @param k
	 *            key of element being removed
	 * @return tree with node removed
	 */
	private TreeNode<City> removehelp(TreeNode<City> rt, String k) {
		if (rt == null)
			return null;
		if (c.compare(readStringFromPool(rt.key()), k) > 0)
			rt.setLeft(removehelp(rt.left(), k));
		else if (c.compare(readStringFromPool(rt.key()), k) < 0)
			rt.setRight(removehelp(rt.right(), k));
		else // found the node
		{
			if (rt.left() == null)
				return rt.right();
			else if (rt.right() == null)
				return rt.left();
			else // two children
			{
				TreeNode<City> temp = getmin(rt.right());
				rt.setElement(temp.element());
				rt.setKey(temp.key());
				rt.setRight(deletemin(rt.right()));
			}
		}
		return rt;
	}

	private TreeNode<City> removehelp(TreeNode<City> rt, String k, City e) {
		if (rt == null)
			return null;
		if (c.compare(readStringFromPool(rt.key()), k) > 0)
			rt.setLeft(removehelp(rt.left(), k));
		else if (c.compare(readStringFromPool(rt.key()), k) < 0)
			rt.setRight(removehelp(rt.right(), k));
		else // found the node
		{
			if (rt.element() == e) {
				if (rt.left() == null)
					return rt.right();
				else if (rt.right() == null)
					return rt.left();
				else // two children
				{
					TreeNode<City> temp = getmin(rt.right());
					rt.setElement(temp.element());
					rt.setKey(temp.key());
					rt.setRight(deletemin(rt.right()));
				}
			}
			else
			{
				removehelp(rt.left(), k, e);
			}
		}
		return rt;
	}

	private City findhelp(TreeNode<City> rt, String k) {
		if (rt == null)
			return null;
		if (c.compare(readStringFromPool(rt.key()), k) > 0)
			return findhelp(rt.left(), k);
		if (c.compare(readStringFromPool(rt.key()), k) == 0)
			return rt.element();
		else
			return findhelp(rt.right(), k);
	}

	/**
	 * helper method for the findAll method.
	 * 
	 * @param rt
	 *            root of the subtree being searched
	 * @param k
	 *            key of element
	 * @return element with given key k
	 */
	private ArrayList<City> findAllhelp(TreeNode<City> rt, String k) {
		if (rt == null)
			return null;
		if (c.compare(readStringFromPool(rt.key()), k) > 0)
			return findAllhelp(rt.left(), k);
		else if (c.compare(readStringFromPool(rt.key()), k) == 0) {
			return getEquals(rt, k);
		} else
			return findAllhelp(rt.right(), k);
	}

	private ArrayList<City> getEquals(TreeNode<City> rt, String k) {
		ArrayList<City> list = new ArrayList<City>();
		while (rt != null) {
			if (c.compare(readStringFromPool(rt.key()), k) == 0)
				list.add(rt.element());
			else
				break;
			rt = rt.left();
		}
		return list;
	}

	/**
	 * deletes the node with the minimum value.
	 * 
	 * @param rt
	 *            current subtree
	 * @return the current subtree with the minimum removed.
	 */
	private TreeNode<City> deletemin(TreeNode<City> rt) {
		if (rt.left() == null)
			return rt.right();
		rt.setLeft(deletemin(rt.left()));
		return rt;
	}

	/**
	 * finds and returns the minimum node of the subtree
	 * 
	 * @param rt
	 *            current subtree
	 * @return node with min value in the subtree
	 */
	private TreeNode<City> getmin(TreeNode<City> rt) {
		if (rt.left() == null)
			return rt;
		return getmin(rt.left());
	}
	
	private String readStringFromPool(Integer handle) {
		byte[] arr = new byte[256];
		int len = 0;
		try {
			len = pool.read(handle, arr);
		} catch (IOException e) {
			System.err.println("Error while attempting to read string");
		}
		return new String(arr, 0, len);
	}
}
